#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/4/9 13:01|13:01
# @Author  : yangdingyi
# @File    : 22. 括号生成
# @Software: PyCharm
from typing import List


class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        # stack = [('', n, n)]
        # while not stack == []:
        #     item = stack.pop()
        #     ss, an, bn = item
        #     if an == 0 and bn == 0:
        #         ans.append(ss)
        #         continue
        #     if an > 0:
        #         stack.append((ss + '(', an - 1, bn))
        #     if an < bn:
        #         stack.append((ss + ')', an, bn - 1))

        def work(na, nb, s=''):
            if na == nb == 0:
                ans.append(s)
                return
            if na > 0:
                work(na - 1, nb, s + '(')
            if na < nb:
                work(na, nb - 1, s + ')')

        work(n, n)

        return ans


solve = Solution()
n1 = 3
print(n1)
print(solve.generateParenthesis(n1))






